package cacy.leetcode.linkedList;

/**
 * Project: LeetcodePractice
 * Package: cacy.leetcode.practice20250217
 * Class:   Code1287
 * Description:
 * 给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。 *
 * 请你找到并返回这个整数
 * 示例：
 *     输入：arr = [1,2,2,6,6,6,6,7,10]
 *     输出：6
 * 提示：
 *     1 <= arr.length <= 10^4
 *     0 <= arr[i] <= 10^5
 *
 * @Date: 2025/2/17 周一
 * @Time: 12:39
 * @Author: 凯齐
 */

class SolutionA {
    public int findSpecialInteger(int[] arr) {
        int currentNum = arr[0];
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == currentNum) {
                count++;
                if (count * 4 > arr.length) {
                    break;
                }
            } else {
                currentNum = arr[i];
                count = 1;
            }
        }
        return currentNum;
    }
}

class SolutionB {
    public int findSpecialInteger(int[] arr) {
        int arrLength = arr.length;
        int span = arrLength / 4 + 1;
        for (int i = 0; i < arrLength; i += span) {
            int start = binarySearch(arr, arr[i]);
            int end;
            if (arr[i] + 1 > arr[arrLength - 1]) {
                end = arrLength;
            } else {
                end = binarySearch(arr, arr[i] + 1);
            }
            if (end - start >= span) {
                return arr[i];
            }
        }
        return -1;
    }

    public int binarySearch(int[] arr, int num) {
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < num) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }
}

public class Code1287 {
    public static void main(String[] args) {
        SolutionB solution = new SolutionB();
        // Array for question
        int[] arr = {1,2,2,3,3,4,4,4};
        System.out.println(solution.findSpecialInteger(arr));
    }
}
